package demogo

func BinarySearchEqual(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	left := 0
	right := n - 1
	for left <= right {
		mid := left + (right-left)/2
		if a[mid] == v {
			return mid
		} else if a[mid] > v {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

func BinarySearchEqualFirst(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	left := 0
	right := n - 1
	for left <= right {
		mid := left + (right-left)/2
		if a[mid] == v {
			if mid == 0 || a[mid-1] != v {
				return mid
			} else { // mid不是第一个等于的
				right = mid - 1 // 此时只能移动right
			}
		} else if a[mid] > v {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

func BinarySearchEqualLatest(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	left := 0
	right := n - 1
	for left <= right {
		mid := left + (right-left)/2
		if a[mid] == v {
			if mid == n-1 || a[mid+1] != v {
				return mid
			} else { // 此时只能移动left
				left = mid + 1
			}
		} else if a[mid] > v {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return -1
}

// 查找第一个大于等于v的下标
func BinarySearchGEFirst(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	left := 0
	right := n - 1
	for left <= right {
		mid := left + (right-left)/2
		if a[mid] < v {
			left = mid + 1
		} else if a[mid] == v {
			if mid == 0 || a[mid-1] != v {
				return mid
			} else {
				right = mid - 1
			}
		} else {
			if mid == 0 || a[mid-1] < v {
				return mid
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}

// 查找最后一个小于等于v的下标
func BinarySearchLELatest(a []int, v int) int {
	n := len(a)
	if n == 0 {
		return -1
	}
	left := 0
	right := n - 1
	for left <= right {
		mid := left + (right-left)/2
		if a[mid] > v {
			right = mid - 1
		} else if a[mid] == v {
			if mid == n-1 || a[mid+1] != v {
				return mid
			} else {
				left = mid + 1
			}
		} else {
			if mid == n-1 || a[mid+1] > v {
				return mid
			} else {
				left = mid + 1
			}
		}
	}
	return -1
}
